package arrays;

import java.util.ArrayList;
import java.util.List;

/**
 * @author pengfei.hpf
 * @date 2020/3/6
 * @verdion 1.0.0
 * 面试题57 - II. 和为s的连续正数序列
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 * 示例 2：
 *
 * 输入：target = 15
 * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 *
 *
 * 限制：
 *
 * 1 <= target <= 10^5
 */
public class FindContinuousSequence {

    //TODO: 利用数学公式啊!!! 你傻了吗 (start + end) * (end - start +1) / 2
    public int[][] findContinuousSequence(int target) {
        if(target <= 2){
            return new int[0][0];
        }
        List<int[]> list = new ArrayList<>();
        int[] sum = new int[target/2 + 1];
        sum[0] = 1;
        int index = -1;
        for(int i = 2; i <= target/2+1; i++){
            sum[i -1] += sum[i -2] + i;
            if(sum[i -1] >= target){
                int cur = sum[i -1];
                if(cur > target){
                    while(index < 0 || cur - sum[index] > target){
                        index ++;
                    }
                    cur = cur - sum[index];
                }
                if(cur == target){
                    list.add(buildArray(index + 2, i));
                }
            }
        }
        int[][] res = new int[list.size()][];
        int i = 0;
        for(int[] ar: list){
            res[i] = (int[])ar;
            i ++;
        }
        return res;
    }

    private int[] buildArray(int start, int end){
        int[] array = new int[end - start + 1];
        int index = 0;
        for(int i = start; i <= end; i ++){
            array[index] = i;
            index ++;
        }
        return array;
    }
}
